/* 131. 分割回文串 */
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    if (s.length === 1) return [[s]]
    const n = s.length
    const f = new Array(n).fill(0).map(() => new Array(n).fill(true))
    const ret = [], ans = []
    const dfs = (i) => {
        if (i == n) {
            /* ans.slice():拷贝了一份 ans */
            ret.push(ans.slice())
            return
        }
        for (let j = i; j < n; j++) {
            if (f[i][j]) {
                ans.push(s.slice(i, j + 1))
                dfs(j + 1)
                ans.pop()
            }
        }
    }
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            /* 
                必须两个字符相等 ^ s[i+1][j-1] 去掉首位也是回文
            */
            f[i][j] = (s[i] === s[j]) && f[i + 1][j - 1]
        }
    }

    dfs(0)

    return ret
};
partition('aab')
